package com.xigua._搜索或回溯算法;

import com.xigua.TreeNode;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 剑指 Offer 36. 二叉搜索树与双向链表
 * @date 2022/3/209:31
 */
public class _剑指Offer_36_二叉搜索树与双向链表 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(2,new TreeNode(1),new TreeNode(3));
        TreeNode right = new TreeNode(5);
        root.left = left;
        root.right = right;
        treeToDoublyList(root);

    }
        static TreeNode end;
        static TreeNode head;
    public static TreeNode treeToDoublyList(TreeNode root) {
        if (root == null) return null;
        dfs(root);
        head.left = end;
        end.right = head;
        return head;
    }
    static void dfs(TreeNode cur){
        if (cur == null) return;
        dfs(cur.left);
        if (end == null) head = cur;
        else end.right = cur;
        cur.left = end;
        end = cur;
        dfs(cur.right);

    }

}
